package day001;


/**
 * 状态压缩
 * <p>
 * 可以用状态压缩来缩小DP table的大小，只记录必要的数据。
 */
public class FibonacciSequence3 {
    public static void main(String[] args) {
        System.out.println(fib(10));
    }

    static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
}
